In our modern communication systems like Internet, cell phone, etc, to protect the secrecy of the information concerned, we need to encrypt the message. There are two different ways to do this. In the first case, we use symmetric cryptosystems to perform this task, where the sender uses the same key to encrypt the message as the key that the receiver uses to decrypt the message. Symmetric systems demand that the sender and the receiver have a way to exchange such a shared key securely. In an open communication channel without any central authority, like wireless communication, this demands a way to perform such a key exchange (KE) in the open between two parties. In a system with a central server, like a cell phone system within one cell company, this demands an efficient and easy to use key exchange system between the server and the clients.
This invention is related to the construction of an authenticated key exchange (KE) systems, where the authentication is achieved using a simple password. Such a system is very useful for many applications, in particular, the case where a client wants to communicate securely with a server, and where the only share secret is the password or certain hash value of a password. We call such a key exchange a password-authenticated key exchange (PAKE).
PAKE systems were proposed in [BMc], [Mc], whose security is based on the hardness of discrete logarithm problems. This system can be broken by future quantum computers as showed in the work of Shor [SHO].
In this invention, we construct new PAKEs that can resist quantum computer attacks use the LWE problem. The invention is based on the new KE from the LWE problem first constructed in the US Patent “Cryptographic systems using pairing with errors” with U.S. Pat. No. 9,246,675.